package sort.basic_sort;

import java.util.Arrays;

/**
 * @author dx
 * @version 1.0
 * @date 2022/4/14 11:00
 * @description: 直接插入排序的思想：将数组中的所有元素依此跟前面已经排好的元素相比较，
 * 如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止
 */
public class Insert_sort {
    public static void main(String[]args){
        int []test ={1,9,5,4,7,2,0,10,5,3};
        insertionSort(test);
    }
    public static void insertionSort(int[] arr){
        for(int i =1;i<arr.length;i++){   //从第2个元素开始取元素，默认第一个元素是排好顺序的数组
            int temp = arr[i];           //取下一个元素，开始 选择 插入到 合适的位置
            for(int j =i;j>=0;j--){      //从后 往前开始遍历前面的数组 比较 取出来的这个待插入的元素
                if(j>0&&arr[j-1]>temp){   //如果取出来的元素 比 待插入的元素要大                （待插入元素更小一些，则后移前一个元素，一直这样比较）
                    arr[j] = arr[j-1];    //就把该元素的【值】后移到后面                                 |
                    System.out.println("Teping"+ Arrays.toString(arr));
                }else {   //如果                                                            (一直到待插入元素比前一个元素小了，则把待插入元素放到该元素后)
                    arr[j] = temp;
                    System.out.println("Sort:"+Arrays.toString(arr));
                    break;
                }
            }
        }
    }

}
/*
result_process:
Sort:[1, 9, 5, 4, 7, 2, 0, 10, 5, 3]
Teping[1, 9, 9, 4, 7, 2, 0, 10, 5, 3]
Sort:[1, 5, 9, 4, 7, 2, 0, 10, 5, 3]
Teping[1, 5, 9, 9, 7, 2, 0, 10, 5, 3]
Teping[1, 5, 5, 9, 7, 2, 0, 10, 5, 3]
Sort:[1, 4, 5, 9, 7, 2, 0, 10, 5, 3]
Teping[1, 4, 5, 9, 9, 2, 0, 10, 5, 3]
Sort:[1, 4, 5, 7, 9, 2, 0, 10, 5, 3]
Teping[1, 4, 5, 7, 9, 9, 0, 10, 5, 3]
Teping[1, 4, 5, 7, 7, 9, 0, 10, 5, 3]
Teping[1, 4, 5, 5, 7, 9, 0, 10, 5, 3]
Teping[1, 4, 4, 5, 7, 9, 0, 10, 5, 3]
Sort:[1, 2, 4, 5, 7, 9, 0, 10, 5, 3]
Teping[1, 2, 4, 5, 7, 9, 9, 10, 5, 3]
Teping[1, 2, 4, 5, 7, 7, 9, 10, 5, 3]
Teping[1, 2, 4, 5, 5, 7, 9, 10, 5, 3]
Teping[1, 2, 4, 4, 5, 7, 9, 10, 5, 3]
Teping[1, 2, 2, 4, 5, 7, 9, 10, 5, 3]
Teping[1, 1, 2, 4, 5, 7, 9, 10, 5, 3]
Sort:[0, 1, 2, 4, 5, 7, 9, 10, 5, 3]
Sort:[0, 1, 2, 4, 5, 7, 9, 10, 5, 3]
Teping[0, 1, 2, 4, 5, 7, 9, 10, 10, 3]
Teping[0, 1, 2, 4, 5, 7, 9, 9, 10, 3]
Teping[0, 1, 2, 4, 5, 7, 7, 9, 10, 3]
Sort:[0, 1, 2, 4, 5, 5, 7, 9, 10, 3]
Teping[0, 1, 2, 4, 5, 5, 7, 9, 10, 10]
Teping[0, 1, 2, 4, 5, 5, 7, 9, 9, 10]
Teping[0, 1, 2, 4, 5, 5, 7, 7, 9, 10]
Teping[0, 1, 2, 4, 5, 5, 5, 7, 9, 10]
Teping[0, 1, 2, 4, 5, 5, 5, 7, 9, 10]
Teping[0, 1, 2, 4, 4, 5, 5, 7, 9, 10]
Sort:[0, 1, 2, 3, 4, 5, 5, 7, 9, 10]
最好的情况下，排序前对象已经按照要求的排序，比较次数:n-1,,移动次数为0，对应的时间复杂度是O(n)
最坏的情况，排序前对象要求的顺序的反序，对应的时间复杂度是O(n^2)
平均时间复杂度为O(n^2)
 */
